package exist79;

public class Exist {
    //采用回溯，递归 进行像某个元素四周进行查找。查找前注意保存当前位置
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j] == word.charAt(0)){
                    if(dfs(board,word,i,j,0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board,String word,int i,int j,int k){

        boolean res = false;
        if(k == word.length()){
            return true;
        }
        //判断条件
        if(i<board.length && i>=0 && j<board[0].length&& j>=0 && board[i][j]==word.charAt(k)){
            //准备开始向四周寻找，先保存当前位置值
            char temp = board[i][j];
            board[i][j] = '0';
            if (
                    dfs(board,word,i-1,j,k+1) ||
                    dfs(board,word,i+1,j,k+1) ||
                    dfs(board,word,i,j-1,k+1)||
                    dfs(board,word,i,j+1,k+1)) {
                res = true;
            }
            board[i][j] = temp;

        }

        return res;

    }

    public static void main(String[] args) {
        Exist exist = new Exist();
        char[][] a = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        System.out.println(exist.exist(a,"ABCC"));

    }

}
